1. Field of the Invention
The present invention relates to the collecting of information relating to the use of a communications bus, which is commonly called network statistics. More particularly, the present invention relates to a packet network protocol analyzer that utilizes a content addressable memory (CAM).
2. Statement of the Problem
Communication systems in which information is transmitted in data packages between a header and trailer that provide information regarding the data package are generally called packet networks. There are many kinds of packets that can be sent over a given packet network, each of which is defined by a set of rules or conventions called protocols. A packet or frame generally includes a header, a trailer, and a payload sandwiched between the header and trailer. The protocol for a given packet, or frame, generally defines the content of the frame header and frame trailers, as well as the relative position of the data package, or payload, in the frame. Protocol analyzers connect to the communications bus of a packet network and collect and store information relating to the packets that are traveling on the bus. Such information may include the type of packet, for example, IBM, Novell, or Appletalk, the number of bits in the frame, and many other types of information. This information is useful for network designers and supervisors in determining equipment requirements, the source of network problems, and generally in supervising the network.
Traditionally, protocol analyzers have utilized microprocessors programmed by software to collect and store the packet information. State-of-the-art data communication networks are very fast, with data transfer at the rate of gigabits per second. Software-based systems cannot keep up with the incoming traffic flow in such high-speed data systems. One common prior art solution to this problem is to sample the data. Thus, the data is of a statistical nature, hence the term "network statistics". Such conventional protocol analyzers can be inaccurate and some events may be totally missed. Prior art solutions to this problem also include the use of pre-filtering to discard unwanted frames thus reducing the packet rate before the software processes the traffic. However, if all or a large percentage of the frames are frames that it is desired to sample, then this solution is not workable.
Another solution is the use of a custom integrated circuit (IC) that utilizes an algorithm to direct the sampling in a manner that selects meaningful frames. However, any sampling solution is not acceptable for a protocol analyzer targeted at the R&D market. R&D people expect to see absolute measurements and not approximations. Moreover, at gigabit data transfer speeds, the sampling is at such a low rate compared to the traffic rate that the algorithms may no longer be valid for making meaningful measurements.
State machines are generally known in the electronics industry, but these have not been used up to now as protocol analyzers, primarily because there are so many different packet network protocols, and each protocol is quite complex, so that it has come to be believed in the art that a state machine capable of analyzing protocols would be so large and complex that it would be unworkable. Further, new protocols are constantly being introduced and old protocols are constantly changing, and it is known that it is much easier to alter a software program to handle new and revised protocols than to reprogram a state machine, which is essentially hardware.
3. Solution to the Problem
The present invention solves the above and other problems in prior art protocol analyzers and network statistics methods by providing a state machine that collects and stores bus communications data. The state machine is entirely hardware-based, and includes no processors that utilize software. As a result it can operate at gigahertz speeds and does not need to sample data.
The state machine also includes a CAM and a random access memory (RAM) that can be reprogrammed as easily as writing software, and thus constantly changing protocols do not create a problem for the protocol analyzer according to the invention.
The protocol analyzer includes an input buffer, a lookup table and a counter memory. The input buffer includes a frame header buffer. The lookup table comprises a state machine including a CAM and a RAM. A frame is stored in the frame header buffer while the CAM and RAM analyze predetermined portions of it. If a data portion is eight bits or less, it is input into the RAM and the RAM outputs instructions stored at the location indicated by the data portion. If the portion is greater than eight bits, it is input into the CAM, which outputs a RAM address at which corresponding instructions are stored. The instructions can include an instruction to increment a count in a predetermined register of the counter memory; an instruction to add a new count register in the counter memory; an instruction to generate a snapshot trigger to cause a capture RAM to store a specific data segment traveling on the packet network; and an instruction to further analyze the data portion.
The invention provides apparatus for collecting network statistics information on a packet network, the apparatus comprising: an input buffer for storing a data packet traveling on the packet network; an electronic lookup table, communicating with the buffer, for analyzing at least a portion of the data packet and for providing an output signal including a statistics signal representative of the statistics information, the lookup table comprising a state machine; and an electronic memory, communicating with the lookup table, for storing the network statistics. Preferably, the state machine comprises a content addressable memory (CAM). Preferably, the state machine further comprises a random access memory (RAM). Preferably, the input buffer includes a logic unit for inputting the portion of the data packet into the CAM if its number of bits is greater than a predetermined number and inputting the portion of the data packet into the RAM if its number of bits is less than or equal to the predetermined number, and preferably, the predetermined number of bits is eight bits. Preferably, the state machine includes a content addressable memory (CAM) manager logic unit including a CAM and a random access memory (RAM) manager logic unit including a RAM, and the output signal comprises a signal output by the RAM manager logic unit. Preferably, the state machine comprises a field programmable gate array (FPGA). Preferably, the apparatus further includes a capture RAM in communication with the state machine. Preferably, the state machine has an input and an output and the output is electronically connected to the input. Preferably, the output signal comprises an instruction selected from the group consisting of: an instruction to increment a count in a predetermined register of the memory; an instruction to add a new count register in the memory; an instruction to generate a snapshot trigger to cause a capture RAM to store a specific data segment traveling on the packet network; and an instruction to further analyze the data portion. Preferably, there are a plurality of the data packets traveling sequentially on the packet network, the buffer stores the plurality of packets, there are a plurality of the state machines, and different ones of the state machines analyze different ones of the data packets. Preferably, data packet includes a header and the input buffer includes a header buffer for storing the header of the data packet. Preferably, the state machine includes an inter-switch link (ISL) header detector. Preferably, the input buffer includes a first in first out register, commonly referred to as a FIFO. Preferably, the output signal includes a trigger signal and the apparatus includes a logic unit responsive to the trigger signal for storing the peripheral component interconnect (PCI) address of a particular data packet. Preferably, the apparatus includes an internal bus and a multiplexer for multiplexing signals traveling on the packet network onto the internal bus. Preferably, the electronic memory includes a first counter portion and a second counter portion and the apparatus further includes heartbeat control logic for swapping the first counter portion and the second counter portion between an active state in which the counter is used to collect statistics information and an inactive state in which the counter is read. Preferably, the portion of the data packet comprises a first signal located at a first address in the data packet and the output signal includes a delta address signal corresponding to an offset value, and the state machine includes an address generator responsive to the delta address signal for providing an address signal corresponding to a second address in the data packet offset from the first address by the offset value.
In another aspect, the invention provides apparatus for collecting network statistics information on a packet network, the apparatus comprising: a buffer for storing a data packet traveling on the packet network; an electronic lookup table, communicating with the buffer, for analyzing at least a portion of the data packet and for providing an output signal including a statistics signal representative of the statistics information, the lookup table comprising a content addressable memory (CAM); and a first electronic memory, communicating with the lookup table, for storing the network statistics. Preferably, the state machine includes a second electronic memory, and the output signal comprises an address in the second electronic memory. Preferably, the lookup table includes a signal selector for outputting a predetermined signal if the portion of the data packet does not match data in the CAM. Preferably, the lookup table includes a logic unit for writing information to the CAM and the signal includes an instruction to the logic unit to cause it to write a new content pattern into the CAM, the new content pattern corresponding to a portion of the data packet pattern traveling on the packet network that was not previously seen by the apparatus.
In a further aspect, the invention provides apparatus for collecting network statistics information on a packet network, the apparatus comprising: a buffer for storing a data packet traveling on the packet network; an electronic lookup table, communicating with the buffer, for analyzing a first portion of the data packet located at a first address and providing an address offset value, for analyzing a second portion of the data packet located at an address offset from the first address by the offset value, and for providing and a network statistics signal representative of the statistics information; an electronic memory, response to the network statistics signal, for storing the network statistics. Preferably, the lookup table comprises: a content addressable memory (CAM) and a random access memory (RAM) for providing a delta address signal corresponding to the offset value; and an address generator response to the delta address signal for generating the address of the second portion of the data packet.
In still another aspect the invention provides a method of collecting network statistics information on a packet network, the method comprising: storing a data packet traveling on the packet network in a buffer; inputting a first signal representing a portion of the data packet located at a first address into an electronic state machine to produce a delta address signal corresponding to an offset value; inputting a second signal representing a portion of the data packet located at a second address offset from the first address by the offset value into the electronic state machine to produce a statistics information signal; and storing a signal related to the statistics information signal in an electronic memory, thereby recording the network statistics.
In yet a further aspect, the invention provides a method of collecting network statistics information on a packet network, the method comprising: storing a data packet traveling on the packet network in a buffer; inputting a first signal representing at least a portion of the data packet into an electronic state machine causing the state machine to output a second signal; and storing a signal related to the second signal in an electronic memory, thereby recording the network statistics. Preferably, the step of inputting and causing comprises inputting the second signal back into the state machine causing it to output a third signal. Preferably, the electronic state machine is capable of a CAM cycle in which a signal input into the state machine is input into a content addressable memory (CAM) and a RAM cycle in which a signal input into the state machine is input into a random access memory (RAM), wherein the second signal includes an instruction as to whether the next cycle to be executed by the state machine is a CAM cycle or a RAM cycle, and the step of inputting the second signal comprises inputting the instruction thereby causing the state machine to execute a predetermined one of the CAM and RAM cycles. Preferably, the step of inputting comprises inputting the first signal into a content addressable memory (CAM) causing the CAM to output an address and inputting the address into a random access memory (RAM) and causing the RAM to output the second signal.